package leetcode;

import model.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Lc94 {

    public List<Integer> inorderTraversal2(TreeNode root) {
        // 对于所给节点，要一穿到底
        // 从最基本的原理出发，能推出来吗？
        // 给一个节点，先将其左树放入
        // 把要访问的节点入栈，然后从栈中取数据
        // 优先入左，再入右
        List<Integer> res  = new ArrayList<>();
        if(root==null){
            return  res;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();

        while(!stack.isEmpty()) {
            root = stack.peek();
            while (root.left != null) {
                stack.push(root.left);
                root = root.left;
            }
            stack.pop(); // 取出来访问
            res.add(root.val);
            if (root.right != null) {
                stack.push(root.right);
            }
        }
        return res;

    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=  new ArrayList<>();
        if(root==null){
            return res;
        }
        // 到底应该用栈，还是队列
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);

        while(stack.size()>0){
            TreeNode node= stack.peek();
            System.out.println(stack.size());

            // 这里存在一个bug
            // 可能left已经访问了
            // 使用一个标记，就可以防止重复访问
            if(node.left!=null){
                stack.push(node.left);
            }else{
                stack.pop();
                res.add(node.val);
                if(node.right!=null){
                    stack.push(node.right);
                }
            }
        }
        return res;
    }
}
